package com.pan.alg.niuke.tree;

import java.util.*;

/**
 * 描述
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 *
 * 数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
 * 要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)
 * 例如：
 * 给定的二叉树是{1,2,3,#,#,4,5}
 */
public class TreePrintZ {

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if(pRoot==null){
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        int level=0;
        queue.offer(pRoot);
        while(!queue.isEmpty()){
            ArrayList<Integer> nodeVal = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i <size ; i++) {
                TreeNode treeNode = queue.poll();
                nodeVal.add(treeNode.val);
                if(treeNode!=null){
                    if(treeNode.left!=null){
                        queue.offer(treeNode.left);
                    }
                    if(treeNode.right!=null){
                        queue.offer(treeNode.right);
                    }
                }
            }

            if(level%2==1){
                Collections.reverse(nodeVal);
            }
            level++;
            result.add(nodeVal);
        }

        return result;
    }

}
